// encode: utf-8 (It is best to open using vscode)
// reference video: https://www.bilibili.com/video/BV1ey4y1d7oD

#include <iostream>
#include <string>

class Solution
{
private:
    int m_Flag[128][128]{};
    int m_Count[128][128]{};

public:
    int LCSLength(char str1[], int len1, char str2[], int len2)
    {
        for (int i = 1; i <= len1; i++)
        {
            for (int j = 1; j <= len2; j++)
            {
                if (str1[i] == str2[j])
                {
                    m_Count[i][j] = 1 + m_Count[i - 1][j - 1];
                    m_Flag[i][j] = 1;
                }
                else
                {
                    // if (m_Count[i - 1][j] < m_Count[i][j - 1]) // bcba
                    if (m_Count[i - 1][j] <= m_Count[i][j - 1]) // bdab
                    {
                        m_Count[i][j] = m_Count[i][j - 1];
                        m_Flag[i][j] = 2;
                    }
                    else
                    {
                        m_Count[i][j] = m_Count[i - 1][j];
                        m_Flag[i][j] = 3;
                    }
                }
            }
        }
        return m_Count[len1][len2];
    }

    void LCS(int i, int j, char str[])
    {
        std::string res = "";
        while (0 != i && 0 != j)
        {
            if (m_Flag[i][j] == 1)
            {
                i = i - 1;
                j = j - 1;
                res = str[j + 1] + res; // when str[] is str2
                // res = str[i + 1] + res // when str[] is str1
            }
            else if (m_Flag[i][j] == 2)
            {
                j = j - 1;
            }
            else if (m_Flag[i][j] == 3)
            {
                i = i - 1;
            }

            // std::cout << i << " " << j << std::endl;
        }
        std::cout << res << std::endl;
    }

    void Print(int len1, int len2)
    {
        std::cout << "-----------------------" << std::endl;

        for (int i = 0; i <= len1; i++)
        {
            for (int j = 0; j <= len2; j++)
            {
                std::cout << m_Count[i][j] << " ";
            }
            std::cout << std::endl;
        }

        std::cout << "-----------------------" << std::endl;

        for (int i = 0; i <= len1; i++)
        {
            for (int j = 0; j <= len2; j++)
            {
                std::cout << m_Flag[i][j] << " ";
            }
            std::cout << std::endl;
        }

        std::cout << "-----------------------" << std::endl;
    }
};

int main()
{
    Solution slt;
    char str1[128], str2[128];
    int len1, len2, len3;
    std::cout << "Please input the first string:" << std::endl;
    std::cin >> len1 >> str1 + 1;
    std::cout << "Please input the second string:" << std::endl;
    std::cin >> len2 >> str2 + 1;
    std::cout << "LCS:" << std::endl;
    len3 = slt.LCSLength(str1, len1, str2, len2);
    slt.Print(len1, len2);
    slt.LCS(len1, len2, str2);
    std::cout << "LCS's Length:" << len3 << std::endl;
}
